Nearly all forms of electronic communication and storage systems use error-correcting codes. Error correcting codes compensate for the intrinsic unreliability of information transfer in these systems by introducing redundancy into the data stream. The mathematical foundations of error correcting were established by the Shannon-Hartley theorem, which defines for the channel, a quantity that specifies the maximum rate at which information can be reliably delivered through the channel.
Reliable transmission at rates approaching capacity generally requires the use of error correcting codes. Thus, error-correcting codes are designed to achieve sufficient reliability while approaching maximum channel capacity. The complexity of implementing the error correcting code is an additional factor that frequently comes into play in practical applications of error correcting codes. Recent advances in error correcting coding systems resulting from the invention of turbo codes and the subsequent rediscovery and development of low-density parity-check (“LDPC”) that can allow systems to approach the Shannon-Hartley theorem capacity while maintaining a reasonably practical level of complexity.
LDPC codes are defined by a sparse parity-check matrix H. Conventionally, this sparse matrix is often randomly generated, subject to the sparsity constraints. A valid codeword, x, based on a given parity check matrix, H, satisfies the condition 0=Hx, where 0 is the all-zeros vector. FIG. 1 illustrates an example sparse parity check matrix H for an LDPC code having a length of 12 (i.e., 12 columns in the matrix). Each row of the parity check matrix H represents a set of check equations that XOR to 0. LDPC codes are capacity-approaching codes, which means that practical constructions exist that allow the noise threshold to be set very close to Shannon's limit) for a symmetric, memoryless channel.
LDPC codes may also be represented by bipartite graphs, often called Tanner graphs. FIG. 2 illustrates an example Tanner graph 20. Tanner graph 20 represents the parity check matrix, H, in which one set of nodes, the variable nodes 22, corresponds to bits of the codeword, and the other set of nodes, the check nodes 26, sometimes called constraint nodes, correspond to the set of parity check constraints that define the code. Edges 24 in the graph connect variable nodes 22 to check nodes 26. A variable node and a check node are said to be neighbors if they are connected by an edge in the graph. The number of connections of a check node is called the check node degree or row weight. In operation, a decoder calculates a log-likelihood ratio (“LLR”) for each of the bits according to variable nodes 22 connected by an edge 24 with a particular check node 26. The calculation is an iterative process that takes into account LLR values associated with each of the other variable nodes 22. Because the process is iterative, the calculation of the LLRs for each variable node 22 continues in successive passes, updating the LLR value associated with each variable node 22 associated with one check node until the criteria for stopping the process has been achieved.
Because the LLR value of each of the variable nodes 22 involved in the process is recalculated and updated during the calculation, each variable node 22 can only be involved in one calculation at a time in a layered decoding architecture. That is, the calculation that is being done on the variable nodes 22 connected by edges 24 to a first check node 26a cannot be done simultaneously in a second check node operating on any of the same variable nodes 22. For example, variable node 22a is connected by an edge 24a to check node 26a. However, variable node 22a is also connected by an edge 24b to check node 26d. And yet, none of the same variable nodes 22 are connected to both check node 26a and check node 26b. Accordingly, the LLR can be calculated for all of the variable nodes 22 connected to check node 26a and check node 26b, but cannot be simultaneously calculated for all of the variable nodes connected to check node 26a and check node 26d (since at least one variable node 22a is connected to both check node 26a and check node 26d).
In the example of both FIG. 1 and FIG. 2, there is no common variable node 22 connected to both check node 26a and check node 26b. Likewise, there is no common variable node 22 between check node 26c and check node 26d, nor between check node 26e and check node 26f. Accordingly, the LLR calculation in this case can be performed by each such pair of check nodes simultaneously using two parallel sets of hardware (one set of hardware for calculating the LLRs associated with the variable nodes connected to the first check node 26a and the other set of hardware to calculate the LLRs associated with the variable nodes connected to the second check node 26b). Once the LLRs for the variable nodes 22 connected to the first pair 26a, 26b have been calculated in association with the first pair of check nodes 26a, 26b, hardware can be use to calculate the LLRs for the variable nodes 22 in connection with the second pair of check nodes 26c, 26d. It should be noted that each check node 26 is connected to four variable nodes 22. Accordingly, LLRs for eight of the twelve variable nodes 22 can be calculated at a time.
LDCP codes are used by a variety of communication devices and networks. One example of such a network is a network that operates in accordance to the Media over Coax Alliance (“MoCA”) MAC/PHY Specification. In a single channel MoCA network, for example, the process of transmitting an aggregate data packet (A-PDU) over the network includes these steps:                A transmitting node requests a time slot for the transmission;        A Network Controller (NC) grants the request if channel resources are available;        The transmitting and receiving nodes transmit and receive packets at the specified times.        
For this process to be successful, both the transmitter and the receiver independently calculate the appropriate LDPC forward error correction code parameters and the number of padding bits to be used. However, the existing Moca 2 parity check matrix has a lower triangular structure such that the reduced connection to other parts of the codeword results in more decoding errors in the parity bits leading to possibly more decoding iterations. This is especially true in the last parity column where column weight is one. Accordingly, a more robust parity check matrix can be provided.